package com.xiaolin.structure.stack.monotone;

import java.util.LinkedList;
import java.util.Stack;

/**
 * @ClassName MonotoneIncreaseStack
 * @Description 单调栈-单调递增
 * @Detail 所谓单调栈就是在栈先进后出的特性之外再添加一个特性：从栈顶到栈底的元素严格递增（or递减）。
 *              特点：
 *                  1、栈内元素保持单调，有单调递增栈和单调递减栈。
 *                  2、每个元素都要入栈，且仅入栈一次，出栈后不再入栈。
 *              注意：
 *                  栈内可以直接存储元素，也可以存储元素的索引，一般存储的是索引。当存储的是索引时，是说索引对应的元素是单调的，而不是说索引是单调的。
 *              操作规则（以单调递增栈为例，单调递减栈相反）：
 *                  设当前进栈元素为 e，如果 e 小于栈顶元素，就直接入栈；如果 e 大于或等于栈顶元素，那就一直弹栈，直到栈顶元素大于 e 或者栈为空时，再将 e 入栈。
 * @Author MyPC
 * @Date 2020/12/12
 * @Version 1.0
 */
public class MonotoneIncreaseStack {
    public static void main(String[] args) {
        int[] arr=new int[]{3,4,2,6,4,5,2,3};
        LinkedList monotoneIncreaseStack = getMonotoneIncreaseStack(arr);
        while (monotoneIncreaseStack.peek()!=null){
            System.out.println(arr[(int)monotoneIncreaseStack.pop()]);
        }
    }

    /**
     * 生成单调递增栈
     * @param arr
     * @return
     */
    public static LinkedList getMonotoneIncreaseStack(int[] arr){
        LinkedList<Integer> stack=new LinkedList<>();
        int index=0;
        while (index < arr.length){
            // 当栈顶不为空而且栈顶元素小于或等于要压入的元素时
            while (stack.peek()!=null && arr[stack.peek()] <= arr[index]){
                // 弹出栈顶元素
                stack.pop();
            }
            //在栈顶添加元素
            stack.push(index++);
        }
        return stack;
    }
}
